SherbyNet - /page/wikibook/entry.mu

Micron Document

<!DOCTYPE html>

<title>Base de Gröbner</title>

</head>

<h1 id="firstHeading" class="firstHeading mw-first-heading">Base de Gröbner</h1>

</header>

</div>

En <a href="Math%C3%A9matiques" title="Mathématiques">mathématiques</a>, une base de Gröbner (ou base standard, ou base de Buchberger) d'un <a href="Id%C3%A9al" title="Idéal">idéal</a> I de l'<a href="Anneau_unitaire" title="Anneau unitaire">anneau</a> de <a href="Polyn%C3%B4me" title="Polynôme">polynômes</a> K[X1, …, Xn] est un ensemble de générateurs de cet idéal, vérifiant certaines propriétés supplémentaires. Cette notion a été introduite dans les années 1960, indépendamment par <a href="Heisuke_Hironaka" title="Heisuke Hironaka">Heisuke Hironaka</a> et <a href="Bruno_Buchberger" title="Bruno Buchberger">Bruno Buchberger</a>, qui lui a donné le nom de son <a href="Directeur_de_th%C3%A8se" title="Directeur de thèse">directeur de thèse</a> <a href="Wolfgang_Gr%C3%B6bner" title="Wolfgang Gröbner">Wolfgang Gröbner</a>.

Les bases de Gröbner ont le grand avantage de ramener l'étude des idéaux polynomiaux à l'étude des idéaux monomiaux (c'est-à-dire formés de <a href="Mon%C3%B4me_(math%C3%A9matiques)" title="Monôme (mathématiques)">monômes</a>), plus faciles à appréhender.

<div class="mw-heading mw-heading2"><h2 id="Intérêt">Intérêt</h2></div>

Soit K un <a href="Corps_commutatif" title="Corps commutatif">corps commutatif</a>.

Dans le cas des polynômes à une seule variable, l'anneau des polynômes à une variable K[X] est <a href="Anneau_euclidien" title="Anneau euclidien">euclidien</a>, et un idéal I de K[X] se représente naturellement par son générateur principal. Plus précisément, l'<a href="Algorithme_d'Euclide" title="Algorithme d'Euclide">algorithme d'Euclide</a> permet de déterminer celui-ci à partir d'une famille finie de générateurs, et ainsi de tester l'appartenance d'un polynôme à I, ou encore de calculer un représentant canonique pour un élément de K[X]/I.

L'anneau des polynômes à n variables K[X1, …, Xn], en revanche, est <a href="Anneau_factoriel" title="Anneau factoriel">factoriel</a> et <a href="Anneau_noeth%C3%A9rien" title="Anneau noethérien">nœthérien</a> mais pas <a href="Anneau_principal" title="Anneau principal">principal</a>. Concrètement, on ne peut pas y étendre « naturellement » la division euclidienne des polynômes à une variable. Les bases de Gröbner permettent néanmoins de calculer modulo un idéal de K[X1, …, Xn], et notamment :

<ul><li>de décider si l'idéal est K[X1, …, Xn] tout entier (c'est-à-dire d'un point de vue géométrique si sa <a href="Vari%C3%A9t%C3%A9_alg%C3%A9brique" title="Variété algébrique">variété</a> dans une <a href="Cl%C3%B4ture_alg%C3%A9brique" title="Clôture algébrique">clôture algébrique</a> de K est vide, ou encore si un système polynomial donné y admet au moins une solution) ;</li>

<li>de décider si un polynôme appartient à l'idéal, ou à son <a href="Radical_d'un_id%C3%A9al" title="Radical d'un idéal">radical</a> — et ainsi, si une <a href="Fonction_polynomiale" title="Fonction polynomiale">fonction polynomiale</a> est nulle sur une variété ;</li>

<li>de trouver des représentants canoniques pour les éléments de l'algèbre quotient, et partant, d'effectuer des calculs algébriques modulo l'idéal ;</li>

<li>de déterminer la dimension et le degré d'une variété équidimensionnelle <a href="https://en.wikipedia.org/wiki/Equidimensionality" class="extiw external" title="en:Equidimensionality">(en)</a> (ou plus généralement la dimension et la somme des degrés des composantes équidimensionnelles de dimension maximale d'une variété quelconque).</li></ul>

Plus généralement, les bases de Gröbner permettent de calculer la fonction et le polynôme de Hilbert <a href="https://en.wikipedia.org/wiki/Hilbert_series_and_Hilbert_polynomial" class="extiw external" title="en:Hilbert series and Hilbert polynomial">(en)</a> d'un <a href="Alg%C3%A8bre_gradu%C3%A9e" title="Algèbre graduée">module gradué</a>. Elles fournissent aussi un moyen de déterminer l'intersection de deux idéaux.

<div class="mw-heading mw-heading2"><h2 id="Définition">Définition</h2></div>

Une façon commode de définir les bases de Gröbner est de faire appel au vocabulaire de la <a href="R%C3%A9%C3%A9criture_(informatique)" title="Réécriture (informatique)">réécriture</a>. C'est l'approche que nous allons adopter ; cependant, l'essentiel des définitions devrait être compréhensible sans connaissance de ces notions.

<div class="mw-heading mw-heading3"><h3 id="Règle_de_réduction">Règle de réduction</h3></div>

Le point de départ est un procédé de réduction qui, à l'instar de la division euclidienne dans K[X], remplace un polynôme par un autre « plus petit » mais équivalent modulo l'idéal. On appelle monôme un polynôme produit d'indéterminées, et terme un monôme multiplié par un scalaire, son coefficient. Pour définir cette « division euclidienne généralisée », il est utile de choisir une façon d'ordonner les monômes de l'anneau considéré (ce dont on se convainc facilement en essayant de diviser un polynôme de K[X, Y] par un autre).

Un <a href="Ordre_monomial" title="Ordre monomial">ordre monomial</a> est un <a href="Ordre_total" title="Ordre total">ordre total</a> sur les monômes tel que

<ul><li>pour tout monôme <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle u}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle u}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/c3e6bb763d22c20916ed4f0bb6bd49d7470cffd8.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.33ex; height:1.676ex;" alt="{\displaystyle u}" loading="lazy">, on ait <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle 1\leq u}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle 1\leq u}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/4226afc557e5789dc67537dbbedaeee32b745f7c.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.505ex; width:5.591ex; height:2.343ex;" alt="{\displaystyle 1\leq u}" loading="lazy"> et</li>

<li>pour tous les monômes <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle u}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle u}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/c3e6bb763d22c20916ed4f0bb6bd49d7470cffd8.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.33ex; height:1.676ex;" alt="{\displaystyle u}" loading="lazy"> et <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle v}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle v}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/e07b00e7fc0847fbd16391c778d65bc25c452597.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.128ex; height:1.676ex;" alt="{\displaystyle v}" loading="lazy"> tels que <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle u\leq v}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle u\leq v}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/fe5730c3f2fd9ab2b37f23c0f5ae368e254aeb9c.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.505ex; width:5.556ex; height:2.176ex;" alt="{\displaystyle u\leq v}" loading="lazy">, on ait <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle uw\leq vw}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle uw\leq vw}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/a6d44e22f47c269bd6aa0349ce2c56e521129921.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.505ex; width:8.884ex; height:2.176ex;" alt="{\displaystyle uw\leq vw}" loading="lazy"> pour tout monôme <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle w}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle w}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/88b1e0c8e1be5ebe69d18a8010676fa42d7961e6.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.664ex; height:1.676ex;" alt="{\displaystyle w}" loading="lazy">.</li></ul>

Un ordre monomial est toujours un <a href="Bon_ordre" class="mw-redirect" title="Bon ordre">bon ordre</a>. On définit naturellement les notions de monôme dominant, de coefficient dominant et de terme dominant — noté ici λ(f) — d'un polynôme f relativement à un ordre monomial.

Par exemple, l'<a href="Ordre_lexicographique" title="Ordre lexicographique">ordre lexicographique</a> est un ordre monomial. D'autres <a href="Relation_d'ordre" title="Relation d'ordre">relations d'ordre</a> sont possibles, pourvu qu'elles vérifient certaines propriétés, destinées à ce que les <a href="Algorithmes" class="mw-redirect" title="Algorithmes">algorithmes</a> de calculs puissent aller à leur terme, sans boucler par exemple. Les relations d'ordre présentent différentes propriétés et donc certains avantages les unes par rapport aux autres, suivant le type de problème posé. Par exemple, l'ordre lexicographique, relativement coûteux en temps de calcul, est assez pratique pour faire des projections de la variété associée à l'idéal.

Fixons un ordre monomial et une partie finie B de K[X1, …, Xn]. Introduisons une <a href="R%C3%A8gles_de_r%C3%A9%C3%A9criture" title="Règles de réécriture">règle de réécriture</a> sur K[X1, …, Xn] en posant

<mfrac>

<mrow>

</mrow>

</mfrac>

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle g\quad \to \quad g-{\frac {t}{\lambda (f)}}\;f}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/afac68c94bea6489020c97096315cbac4f5c2f2f.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -2.671ex; width:20.535ex; height:6.009ex;" alt="{\displaystyle g\quad \to \quad g-{\frac {t}{\lambda (f)}}\;f}" loading="lazy"></dd></dl>

si t est le terme de g de plus haut degré divisible par un certain λ(f) avec f∈B. La <a href="Relation_binaire#Relation_sur_(ou_dans)_un_ensemble" title="Relation binaire">clôture réflexive transitive</a> →* de → est appelée réduction modulo B. Autrement dit, pour réduire g, on essaie de lui retrancher un multiple convenable d'un polynôme f de B, de sorte que les termes dominants se simplifient. (On retrouve ici non seulement la <a href="Division_euclidienne" title="Division euclidienne">division euclidienne</a> pour les polynômes à une variable, mais aussi, dans le cas linéaire, le <a href="%C3%89limination_de_Gauss-Jordan" title="Élimination de Gauss-Jordan">pivot de Gauss</a>.) Si l'on ne parvient pas à éliminer le terme dominant de g, on l'ajoute au « reste » de la division et on passe au terme de degré immédiatement inférieur.

La réduction →* <a href="Terminaison_d'un_syst%C3%A8me_de_r%C3%A9%C3%A9criture" title="Terminaison d'un système de réécriture">termine (elle est « nœthérienne »)</a>, mais elle n'est en général pas <a href="Confluence_(informatique)" title="Confluence (informatique)">confluente</a>, c'est-à-dire que bien que tout polynôme admette une forme réduite modulo B, celle-ci n'a aucune raison d'être unique.

<div class="mw-heading mw-heading3"><h3 id="Bases_de_Gröbner">Bases de Gröbner</h3></div>

Une base de Gröbner est une partie B pour laquelle la situation est plus favorable.

Soit I un idéal de K[X1, …, Xn]. Une base de Gröbner, ou base standard, de I est une <a href="Partie_g%C3%A9n%C3%A9ratrice_d'un_groupe" title="Partie génératrice d'un groupe">partie génératrice</a> finie G de I vérifiant en outre les propriétés équivalentes suivantes.

<ol><li>La réduction modulo G est confluente (et donc fortement normalisante).</li>

<li>Un polynôme g appartient à I si et seulement s'il se réduit à 0 modulo G.</li>

<mfrac>

<mrow>

</mrow>

<mrow>

</mrow>

</mfrac>

</mrow>

<mfrac>

<mrow>

</mrow>

<mrow>

</mrow>

</mfrac>

</mrow>

<msup>

</mrow>

</msup>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle {\frac {\lambda (f)\vee \lambda (g)}{\lambda (f)}}\,f-{\frac {\lambda (f)\vee \lambda (g)}{\lambda (g)}}\,g\quad \to ^{*}\quad 0}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/413210f790efc78ab4c83227f43b5838e22f7273.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -2.671ex; width:40.77ex; height:6.509ex;" alt="{\displaystyle {\frac {\lambda (f)\vee \lambda (g)}{\lambda (f)}}\,f-{\frac {\lambda (f)\vee \lambda (g)}{\lambda (g)}}\,g\quad \to ^{*}\quad 0}" loading="lazy"> modulo G, le symbole ∨ désignant le <a href="Plus_petit_commun_multiple" title="Plus petit commun multiple">ppcm</a> normalisé [pas clair].</li>

<li>Les monômes dominants des polynômes de G engendrent le même idéal que les monômes dominants des éléments de I (cela implique que G engendre I).</li></ol>

Cette dernière propriété est la définition usuelle des bases de Gröbner. Elle est pertinente pour leur étude théorique, mais les deux premières formulations sont peut-être plus parlantes. L'assertion 3 fournit quant à elle un moyen simple pour tester si une famille de polynômes est une base de Gröbner.

On peut montrer que tout idéal admet une base de Gröbner. Avec cette définition, il n'y a pas unicité ; si G est une base de Gröbner de I et si f appartient à I, alors G∪{f} est encore une base de Gröbner de I. En revanche, tout idéal admet une unique base de Gröbner minimale, c'est-à-dire à laquelle on ne peut enlever de polynôme en maintenant la propriété d'être une base de Gröbner de l'idéal.

<div class="mw-heading mw-heading2"><h2 id="Calcul">Calcul</h2></div>

On dispose d'<a href="Algorithmique" title="Algorithmique">algorithmes</a> pour calculer les bases de Gröbner. Très sommairement, le premier et le plus connu, l'<a href="Algorithme_de_Buchberger" title="Algorithme de Buchberger">algorithme de Buchberger</a>, procède en ajoutant des polynômes à la base pour éliminer peu à peu les paires critiques qui contredisent l'assertion 3, un peu à la manière de la <a href="Compl%C3%A9tion_de_Knuth-Bendix" title="Complétion de Knuth-Bendix">complétion de Knuth-Bendix</a>. On sait aussi calculer les bases de Gröbner minimales.

Ces algorithmes sont très inefficaces dans le pire des cas, et les cas plus favorables sont mal connus.

Pour un idéal de polynômes à n variables de degré total borné par D, on sait calculer une base de Gröbner en au plus <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle D^{2^{O(n)}}}">

<msup>

<msup>

</mrow>

</msup>

</mrow>

</msup>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle D^{2^{O(n)}}}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/cd2553f6a000d23620b46bf8064ffed03b3a2774.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:6ex; height:3.176ex;" alt="{\displaystyle D^{2^{O(n)}}}" loading="lazy"> opérations dans le corps de base. Ernst Mayr <a href="https://de.wikipedia.org/wiki/Ernst_Mayr_(Informatiker)" class="extiw external" title="de:Ernst Mayr (Informatiker)">(de)</a> et <a href="Albert_R._Meyer" title="Albert R. Meyer">Albert R. Meyer</a> ont montré[réf. nécessaire] que cette <a href="Borne_sup%C3%A9rieure_et_borne_inf%C3%A9rieure" title="Borne supérieure et borne inférieure">borne supérieure</a> énorme pouvait être atteinte, et donc est optimale : il existe des idéaux dont toute base de Gröbner compte <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle 2^{2^{\Omega (n)}}}">

<msup>

<msup>

</mrow>

</msup>

</mrow>

</msup>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle 2^{2^{\Omega (n)}}}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/be01fb26016ef8e7a1a7951b95a6b3085823bb89.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:5.184ex; height:3.176ex;" alt="{\displaystyle 2^{2^{\Omega (n)}}}" loading="lazy"> éléments, eux-mêmes de degré doublement exponentiel en n. Tout n'est pas perdu pour autant. En effet, expérimentalement, cette borne n'est atteinte que sur les exemples construits dans ce but. Pour un système rationnel ayant un nombre fini de solutions complexes, Daniel Lazard <a href="https://en.wikipedia.org/wiki/Daniel_Lazard" class="extiw external" title="en:Daniel Lazard">(en)</a> a établi que le calcul était faisable en temps DO(n)[réf. nécessaire]. Sous des hypothèses légèrement différentes, <a href="Jean-Charles_Faug%C3%A8re" title="Jean-Charles Faugère">Jean-Charles Faugère</a> donne une borne de O(D4, 3n)[réf. nécessaire]. Mais de façon générale, la complexité du calcul de bases de Gröbner dans les cas usuels est mal maîtrisée.

<div class="mw-heading mw-heading2"><h2 id="Références">Références</h2></div>

<ul><li><abbr class="abbr indicateur-langue" title="Langue : allemand">(de)</abbr> <a href="Bruno_Buchberger" title="Bruno Buchberger">Bruno Buchberger</a>, <a rel="nofollow" class="external text" href="http://www.ricam.oeaw.ac.at/Groebner-Bases-Bibliography/gbbib_files/publication_706.pdf">Ein Algorithmus zum Auffinden der Basiselemente des Restklassenrings nach einem nulldimensionalen Polynmideal</a> (Un algorithme pour déterminer les éléments de base d'un anneau de classes de résidus d'un idéal de polynômes de dimension zéro), thèse présentée en 1965 à l'<a href="Universit%C3%A9_d'Innsbruck" title="Université d'Innsbruck">université d'Innsbruck</a>, où apparaissent pour la première fois les bases de Gröbner ; une traduction en anglais due à Michael Abramson figure dans le <a href="Journal_of_Symbolic_Computation" title="Journal of Symbolic Computation">Journal of Symbolic Computation</a>, vol. 41, 2006, <abbr class="abbr" title="pages">p.</abbr> 471-511.</li>

<li><abbr class="abbr indicateur-langue" title="Langue : anglais">(en)</abbr> <a href="David_Eisenbud" title="David Eisenbud">David Eisenbud</a>, <cite class="italique" lang="en">Commutative Algebra with a View Toward Algebraic Geometry</cite>, <abbr class="abbr" title="collection">coll.</abbr> « <a href="Graduate_Texts_in_Mathematics" title="Graduate Texts in Mathematics">GTM</a> » (<abbr class="abbr" title="numéro">no</abbr> 150), <time>1995</time> (<a rel="nofollow" class="external text" href="https://books.google.com/books?id=Fm_yPgZBucMC&pg=PA321">lire en ligne</a>)<span class="Z3988" title="ctx_ver=Z39.88-2004&rft_val_fmt=info%3Aofi%2Ffmt%3Akev%3Amtx%3Abook&rft.genre=book&rft.btitle=Commutative+Algebra+with+a+View+Toward+Algebraic+Geometry&rft.aulast=Eisenbud&rft.aufirst=David&rft.date=1995&rft_id=%2F%2Fbooks.google.com%2Fbooks%3Fid%3DFm_yPgZBucMC%26pg%3DPA321&rfr_id=info%3Asid%2Ffr.wikipedia.org%3ABase+de+Gr%C3%B6bner"></li></ul>

<ul id="bandeau-portail" class="bandeau-portail"><li> Portail de l’algèbre </li> <li> Portail de l'informatique théorique </li> </ul></div><div><div class="zim-footer">

Cet article est issu de <a class="external text" title="Dernière modification le 2025-04-02" href="https://fr.wikipedia.org/wiki/?title=Base_de_Gr%C3%B6bner&oldid=224482412">Wikipédia</a>. Sauf mention contraire, le texte est disponible sous <a class="external text" href="https://creativecommons.org/licenses/by-sa/4.0/deed.fr">Creative Commons Attribution-Share Alike 4.0</a>. Des conditions supplémentaires peuvent s’appliquer aux fichiers multimédias.

</div>

</div></div>

</div>

</main>

</div>

</body></html>